﻿package com.flashshe.ds.list
{
	

	public class DoublyLinkedList extends AbstractList
	{
		private var head:DoublyLinkedListElement;	
		private var tail:DoublyLinkedListElement;
		private var count:int = 0;
		
		
		public function DoublyLinkedList()
		{
			super();
		}
		
		public override function get size():int
		{
			return count;
		}
		
		public override function clear():void
		{
			head = null;
			tail = null
			count = 0;
		}				
		
		public override function add(v:Object):void
		{			
			if (head == null)
			{
				head = new DoublyLinkedListElement(v);
				tail = head;
			}
			else
			{
				var lastElement:DoublyLinkedListElement = new DoublyLinkedListElement(v, null, tail);
				tail.nextElement = lastElement;
				tail = lastElement;
			}
			
			count += 1;
		}
		
		public override function addAt(index:uint, v:Object):void
		{			
			if (index > size)
			{
				throw new RangeError("提供的索引超出了范围");
			}			
			
			if (head == null)
			{
				add(v);
				return;
			}
			
			
			// 列表中至少有一个元素			
			
			//插入列表头部
			if (0 == index)
			{
				var firstElement:DoublyLinkedListElement = new DoublyLinkedListElement(v, head, null);
				head.previousElement = firstElement;
				head = firstElement;
				count += 1;
				return;
			}
			
			if (index == size)
			{
				add(v);
				return;
			}
			
			// 列表中至少有两个元素并且不会插入头部
			var i:int = 0;			
			var finger:DoublyLinkedListElement = head;
			
			while(finger.nextElement)
			{
				finger = finger.nextElement;
				i += 1;
				if (i == index)
				{
					break;
				}				
			}
			
			var element:DoublyLinkedListElement = new DoublyLinkedListElement(v, finger, finger.previousElement);
			finger.previousElement.nextElement = element;
			finger.previousElement = element;
						
			count += 1;
		}
		
		public override function getValueAt(index:uint):Object
		{
			if (index < 0 || index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}
			
			var finger:DoublyLinkedListElement = head;
			var i:int = 0;
			
			do 
			{
				if (i == index)
				{					
					return finger.value;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i <= index);
			
			return null;
		}
		
		public override function getLast():Object
		{
			if (tail)
			{
				return tail.value;
			}
			
			return null;
		}
		
		public override function removeAt(index:uint):Object
		{
			if (index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}	
			var result:Object;
			
			if (index == 0)
			{
				result = head.value;
				if (size == 1)
				{
					clear();					
				}
				else
				{
					head.nextElement.previousElement = null;
					head = head.nextElement;
				}
				count -= 1;
				return result;
			}
			
			// 列表中至少有两个元素且不会删除第一个元素
			var i:int = 0;			
			var finger:DoublyLinkedListElement = head;
			
			while(finger.nextElement)
			{
				finger = finger.nextElement;
				i += 1;
				if (i == index)
				{
					break;
				}				
			}
			
			result = finger.value;
			if (finger == tail)
			{				
				tail.previousElement.nextElement = null;
				tail = tail.previousElement;				
			}
			else
			{
				finger.previousElement.nextElement = finger.nextElement;
				finger.nextElement.previousElement = finger.previousElement;
			}
						
			count -= 1;
						
			return result;
		}
		
		public override function remove():Object
		{						
			var result:Object = null;
			
			if (size == 0)
			{
				return result;
			}
			
			result = tail.value;
			
			if (size == 1)
			{
				head = null
				tail = null;
				count -= 1;
				
				return result;
			}
			
			tail.previousElement.nextElement = null;
			tail = tail.previousElement;
			count -= 1;
			
			return result;
		}
				
		public override function setValueAt(index:uint, v:Object):Object
		{
			if (index < 0 || index >= size)
			{
				throw new RangeError("在位置" + index + "没有值");
			}
			
			var i:int = 0;			
			var finger:DoublyLinkedListElement = head;
			
			do
			{
				if (i == index)
				{					
					var result:Object = finger.value;
					finger.value = v;
					return result;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i < count);			
			
			return null;
		}							
		
		public override function indexOf(v:Object, startIndex:uint=0):int
		{
			if (count == 0 || startIndex >= count)
			{
				return -1;
			}
			
			var i:int = 0;			
			var finger:DoublyLinkedListElement = head;
			
			do
			{
				if (finger.value == v && i >= startIndex)
				{					
					return i;
				}
				i += 1;
				finger = finger.nextElement;
			}
			while(i < count);
			
			return -1;
		}
		/*public override function iterator():IIterator
		{
			return null;
		}*/
	}
}